package com.salim.leetcode.$147;

public class InsertionSortList {
    public ListNode insertionSortList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode dummy = new ListNode();
        dummy.next = head;
        while (head.next!=null){
            if(head.next.val<head.val){
                ListNode point = dummy;
                while (point.next!=null){
                    if((point==dummy||point.val<head.val) && point.next.val>head.next.val){
                        ListNode pointNextNext = point.next;
                        point.next = head.next;
                        head.next = head.next.next;
                        point.next.next = pointNextNext;
                        break;
                    }else{
                        point = point.next;
                    }
                }
            }else{
                head = head.next;
            }
        }
        return dummy.next;
    }

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
